package or;

import java.util.Arrays;

public class T0233 {
    char[] s;
    int[][] memo;

    public int countDigitOne(int n) {
        s = Integer.toString(n).toCharArray();
        int m = s.length;
        memo = new int[m][10];
        for (int i = 0; i <m ; i++) {
            Arrays.fill(memo[i], -1);
        }


        return dp(0, 0, true, false);
    }


    public int dp(int i, int mask, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            return isNum ? mask : 0;
        }
        if (!isLimit && isNum && memo[i][mask] != -1) {
            return memo[i][mask];
        }

        int res = 0;
        if (!isNum) {
            res = dp(i + 1, mask, false, false);
        }
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = isNum ? 0 : 1; d <= up; d++) {

            res += dp(i + 1, mask + (d == 1 ? 1 : 0), isLimit && d == up, true);
        }
        if (!isLimit && isNum) {
            memo[i][mask] = res;
        }
        return res;
    }
}
